package leetcode.每日一题;

import leetcode.剑指offer.pojo.TreeNode;
import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2022/3/14 20:38
 * @description：https://leetcode-cn.com/problems/recover-binary-search-tree/
 */
public class 恢复二叉搜索树 {
    @Test
    public void test() {
        Solution solution = new Solution();
    }

    /*
    class Solution {
        public void recoverTree(TreeNode root) {
            if (root == null) return;
            List<Integer> list = new ArrayList<>();
            infixOrder(root, list);
            int[] swapped = findTwoSwapped(list);
            recover(root, 2, swapped[0], swapped[1]);
        }

        private void recover(TreeNode node, int count, int x, int y) {
            if (node != null) {
                if (node.val == x || node.val == y) {
                    node.val = node.val == x ? y : x;
                    if (--count == 0) {
                        return;
                    }
                }
                recover(node.left, count, x, y);
                recover(node.right, count, x, y);
            }
        }

        private int[] findTwoSwapped(List<Integer> list) {
            int n = list.size();
            int index2 = -1, index1 = -1;
            for (int i = 0; i < n - 1; i++) {
                if (list.get(i + 1) < list.get(i)) {
                    index2 = i + 1;
                    if (index1 == -1) {
                        index1 = i;
                    } else {
                        break;
                    }
                }
            }
            return new int[]{list.get(index1), list.get(index2)};
        }

        private void infixOrder(TreeNode node, List<Integer> list) {
            if (node.left != null) {
                infixOrder(node.left, list);
            }
            list.add(node.val);
            if (node.right != null) {
                infixOrder(node.right, list);
            }
        }
    }
    */
    class Solution {
        public void recoverTree(TreeNode root) {
            Stack<TreeNode> stack = new Stack<>();
            TreeNode x = null, y = null, pred = null;
            while (!stack.isEmpty() || root != null) {
                while (root != null) {
                    stack.push(root);
                    root = root.left;
                }
                root = stack.pop();
                if (pred != null && root.val < pred.val) {
                    y = root;
                    if (x == null) {
                        x = pred;
                    } else {
                        break;
                    }
                }
                pred = root;
                root = root.right;
            }
            swap(x, y);
        }

        private void swap(TreeNode x, TreeNode y) {
            int tmp = x.val;
            x.val = y.val;
            y.val = tmp;
        }


    }
}
